package LeetCode;

import java.util.Map;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}20:34
 */
public class LeetCode152 {

    public static void main(String[] args) {
        int[] nums = {0,2};
        System.out.println(new LeetCode152().maxProduct(nums));
    }


    //尝试使用滑动窗口但是失败
    /*public int maxProduct(int[] nums) {
        if (nums==null||nums.length == 0){
            return 0;
        }
        if (nums.length == 1){
            return nums[0];
        }
        int max = -Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++){
            if (i == nums.length - 1){
                break;
            }

            int j = i+1;
            max = Math.max(nums[i] * nums[j],max);
            int index = max;
            while (index != max){
                j++;
                if (j > nums.length - 1){
                    break;
                }
                max = Math.max(index * nums[j],max);
            }
        }
        return max;
    }*/

    //一般的无后效性
//    public int maxProduct(int[] nums){
//        int len = nums.length;
//        if (len == 0){
//            return 0;
//        }
//
//        // dp[i][0]；以nums[i] 结尾的连续子数组的最小值
//        // dp[i][1]: 以nums[i] 结尾的连续子数组的最大值
//        int[][] dp = new int[len][2];
//        dp[0][0] = nums[0];
//        dp[0][1] = nums[0];
//        for (int i = 1; i < len; i++){
//            if (nums[i] >= 0){//为正数的时候
//                dp[i][0] = Math.min(nums[i],nums[i] * dp[i -1][0]);//最小值
//                dp[i][1] = Math.max(nums[i],nums[i] * dp[i - 1][1]);
//            }else {//为负数的时候
//                dp[i][0] = Math.min(nums[i],nums[i] * dp[i - 1][1]);
//                dp[i][1] = Math.max(nums[i],nums[i] * dp[i -1][0]);
//            }
//        }
//        int res = dp[0][1];
//        for (int i = 1; i < len; i++) {
//            res = Math.max(res, dp[i][1]);
//        }
//        return res;
//    }


    //表格复用
    public int maxProduct(int[] nums) {
        int len = nums.length;
        if (len == 0){
            return 0;
        }
        int preMax = nums[0];
        int preMin = nums[0];

        //滚动变量
        int curMax;
        int curMin;

        int res = nums[0];
        for (int i = 1; i < len; i++){
            if (nums[i] >= 0){
                curMax = Math.max(preMax * nums[i],nums[i]);
                curMin = Math.min(preMin * nums[i],nums[i]);
            }else {
                curMax = Math.max(preMax * nums[i],nums[i]);
                curMin = Math.min(preMax * nums[i],nums[i]);
            }
            res = Math.max(res,curMax);

            //赋值滚动变量
            preMax = curMax;
            preMin = curMin;
        }
        return res;
    }
}
